import java.util.Arrays;

public class LIS {
    // 最长上升子序列
    // https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int LIS (int[] arr) {
        // write code here
        // dp[i]表示以第i个元素为结尾的最长上升子序列的长度
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        int maxLenght = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    maxLenght = Math.max(maxLenght, dp[i]);
                }
            }
        }
        return maxLenght;
    }
}
